import java.util.*;

public class Leet480 {
    public static void main(String[] args) {
        Leet480 l = new Leet480();
        System.out.println(Arrays.toString(l.medianSlidingWindow(new int[]{2147483647,2147483647,2147483647,2147483647,2147483646, 2147483647,2147483647,2147483647,2147483647}, 3)));
    }
    public double[] medianSlidingWindow(int[] nums, int k) {
        double two = 2;
        double[] d = new double[nums.length-k+1];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++)
            list.add(nums[i]);
        int fir = nums[0];
        Collections.sort(list);
        if (k%2==1){
            d[0] = list.get(k/2);
            for (int i = 1; i < nums.length-k+1; i++) {
                list.remove(Collections.binarySearch(list,fir));
                int t = Collections.binarySearch(list,nums[i+k-1]);
                if (t>=0)
                    list.add(t,nums[i+k-1]);
                else list.add(-t-1,nums[i+k-1]);
                fir = nums[i];
                d[i] = list.get(k/2);
            }
        }
        else{
            long t1 = list.get(k/2),t2 = list.get(k/2-1);
            t1 = t1+t2;
            d[0] = t1/two;
            for (int i = 1; i < nums.length-k+1; i++) {
                list.remove(Collections.binarySearch(list,fir));
                int t = Collections.binarySearch(list,nums[i+k-1]);
                if (t>=0)
                    list.add(t,nums[i+k-1]);
                else list.add(-t-1,nums[i+k-1]);
                t1 = list.get(k/2);
                t2 = list.get(k/2-1);
                t1 = t1+t2;
                d[i] = t1/two;
                fir = nums[i];
            }
        }
        return d;
    }
}
